package algorithm.dynamic;

/**
 * leetcode : https://leetcode.com/problems/unique-paths-ii/description/
 * Difficulty : Medium
 *
 * 求唯一路径条数的问题
 * 与上一题不同的是，这次给一个矩阵，矩阵中有障碍物，通路表示0，障碍物表示1。
 * 需要绕过障碍物
 *
 * 思路：
 * 还是动态规划
 * 其实和上一题思路一样，只不过在障碍物路径为0
 * @Author Antony
 * @Since 2018/7/18 19:08
 */
public class UniquePathsII {

    public static void main(String[] args) {
        int[][] grid = new int[3][3];
        grid[0] = new int[]{0,0,0};
        grid[1] = new int[]{0,1,0};
        grid[2] = new int[]{0,0,0};

        // expect result = 2;
        System.out.println(uniquePathsWithObstacles(grid));

    }

    /**
     * beats 100.0% - 0ms
     * 注意，和上一个问题的区别是：
     * 边界的路径需要计算，而不能默认为1。因为可能在边界上存在障碍物。
     * 注意特殊值的处理
     */
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid.length == 0 || obstacleGrid[0][0]==1) return 0;
        int height = obstacleGrid.length;
        int width = obstacleGrid[0].length;

        int[][] dpPaths = new int[height][width];
        int tmp;
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                if(obstacleGrid[i][j] == 1){
                    tmp = 0;
                }else if(i==0 && j==0){
                    tmp = 1;
                }else {
                    int upPath = i==0 ? 0 : dpPaths[i-1][j];
                    int leftPath = j==0 ? 0 : dpPaths[i][j-1];
                    tmp = upPath + leftPath;
                }
                dpPaths[i][j] = tmp;
            }
        }

        return dpPaths[height-1][width-1];
    }
}
